Caching is used in computing systems to address the discrepancy in access times between main memory and disk. A disk cache keeps frequently-referenced data that are stored on the disk in memory so that requests for those data can be returned immediately from memory without the penalty of a slower disk access. Generally, the total size of data accessed by a computing workload exceeds the size of any practical cache. Thus, any cache, after a short time, becomes full, and decisions must be made as to which data should be kept and consequently which data should be discarded in order to maintain the highest overall utility of the cache. These decisions are made by a caching algorithm or, more specifically, by the replacement policy of such an algorithm.
The general goal of any caching algorithm is to maximize the hit rate of the cache, which is the ratio of how many times a requested datum is found in the cache to the total number of accesses. Because caching algorithms typically operate in real time and without knowledge of which data will be accessed, a caching algorithm generally attempts to maximize the hit rate by making an educated guess about the future value of each datum based on the pattern of past accesses. The future value that is assigned to each cached datum generally is an indicator of the likelihood that a particular datum will be requested sooner than the other data in the cache. Thus, by assigning values in this manner and maintaining an ordering of the cached data in accordance with those values, the datum having the least value will be discarded from the cache (when necessary) and replaced whenever a more valuable datum arrives. Note that a caching algorithm need not explicitly keep the values by storing them in variables.
Implementation of a caching algorithm that manages data stored in a local cache (i.e., a local caching algorithm) need only concern itself with assigning values based on the importance of the cached data to the local computing device. However, in complex high-performance computing clusters having a large number of clients that share a global cache, a cooperative caching algorithm may be implemented which values cached data based on global metrics rather than just purely local concerns. In such embodiments, difficulties may be encountered in determining what data to cache, where to cache it, and how to manage communications among the various peers relating to the cached data.